#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int res=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){res=(res<<1)+(res<<3)+(c^48);c=getchar();}
	return res*f;
}
void write(__int128 x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int c,t;
int n,k;
int a[2000005];
int b[2000005];
int f[2505][5005],g[5005];
int cnt[2000005];
signed main()
{
	freopen("festival.in","r",stdin);
	freopen("festival.out","w",stdout);
	c=read(),t=read();
	while(t--)
	{
		n=read(),k=read();
		int m=0;
		for(int i=1;i<n;i++) a[i]=read(),m=max(m,a[i]);
		for(int i=1;i<=k;i++) b[i]=read();
		for(int i=1;i<=n;i++) cnt[i]=0;
		for(int i=1;i<=n-k+1;i++) 
			for(int j=i;j<=i+k-1;j++) cnt[j]+=b[j-i+1];
		if(c<=6)
		{
			a[0]=m;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=m;j++) f[i][j]=-1e18;
			f[0][0]=0;
			for(int i=0;i<=m;i++) g[i]=0;
			for(int i=1;i<=n;i++)
			{
				for(int j=0;j<=a[i-1];j++)
					f[i][j]=g[a[i-1]-j]+cnt[i]*j;
				for(int j=0;j<=m;j++) g[j]=f[i][j];
				for(int j=1;j<=m;j++) g[j]=max(g[j],g[j-1]); 
			}
			int ans=0;
			for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
			write(ans),puts("");
		}
		else
		{
			__int128 ans=a[1]*cnt[1],now=a[1];
			for(int i=2;i<=n;i++)
			{
				now=a[i-1]-now;
				if(now>a[i]) now=a[i];
				ans+=now*cnt[i];
			}
			write(ans),puts("");
		}
	}
	return 0;
}
/*
0 2
4 2
5 4 2
2 1
7 4
4 8 6 7 8 3
3 5 1 2 
diff festival.out festival2.out -b
*/
